/**
 * @author: 最帅的的乐乐
 * @date: 2024/3/29 16:47
 * @motto the harder, the luckier
 * 创建一个二维布尔数组dp，其中dp[i][j]表示字符串s的前i个字符和模式p的前j个字符是否匹配。
 *
 * 初始化dp[0][0] = true，表示空字符串和空模式是匹配的。
 *
 * 使用两层循环遍历字符串s和模式p的所有可能情况，并根据不同的字符进行匹配判断。
 *
 * 如果当前模式字符为*，则分两种情况考虑：
 *
 * 不使用*，即跳过当前字符和前一个字符，即dp[i][j] = dp[i][j - 2]
 * 使用*，即重复前一个字符（或.）0次或多次，即dp[i][j] = dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.')
 * 如果当前模式字符不为*，则判断当前字符是否匹配：
 *
 * 当前字符相等或模式字符为.时，继续向前匹配：dp[i][j] = dp[i - 1][j - 1]
 * 最终返回dp[m][n]，其中m为字符串s的长度，n为模式p的长度，表示整个字符串和模式是否匹配。
 *
 * 这种动态规划的解法能够高效地处理正则表达式匹配问题，时间复杂度为O(m*n)，其中m为字符串长度，n为模式长度  。
 */

public class _10_IsMatch {
    public static void main(String[] args) {
        String s = "aaa";
        String p = "a*";
        String p1 = "a*";
        _10_IsMatch isMatch = new _10_IsMatch();
        System.out.println(isMatch(s,p));
        boolean a = true;
        a = 0>0;
        System.out.println(a);
    }
    public static boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;

        for (int i = 0; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2] || (i > 0 && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') && dp[i - 1][j]);
                } else {
                    dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.');
                }
            }
        }

        return dp[m][n];
    }
}
